import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class test {
//    public static void main(String[] args){
////        String s1="hello";
////        String s2="hello";
////        String s3=new String("hello");
////        String s4=new String("hello");
////        System.out.println(s1==s2);
////        System.out.println(s1==s3);
////        System.out.println(s3==s4);
//
//        char[] ch=new char[]{'a','b','c'};
//        String s1=new String(ch);
//        s1.intern();
//        String s2="abc";
//        System.out.println(s1==s2);
//    }

    public int numJewelsInStones(String jewels,String stones){
        int count=0;
        Set<Character> set=new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        for (int i = 0; i < stones.length(); i++) {
            char ch=stones.charAt(i);
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    public static void func(String str1,String str2){
        Set<Character> set=new HashSet<>();
        for (char ch:str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> set1=new HashSet<>();
        for (char ch:str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch)&&!set1.contains(ch)){
                set1.add(ch);
                System.out.print(ch);
            }
        }
    }
//    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String str1=sc.nextLine();
//            String str2=sc.nextLine();
//            func(str1,str2);
//        }
//    }


    public static List<String> toKFrequent(String[] words,int k){
        //1、遍历数组统计每个单词出现的频率
        Map<String,Integer> hashMap=new HashMap<>();
        for (String s:words) {
            if(hashMap.get(s)==null){
                hashMap.put(s,1);
            }else{
                hashMap.put(s,hashMap.get(s)+1);
            }
        }
        //2、建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        //3、遍历hashMap 把里面 的数据 放到小根堆
        for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //小根堆放满了K个，下一个entry和堆顶元素比较
                Map.Entry<String, Integer> top = minHeap.peek();
                //堆顶的频率小于当前entry的频率 就出队 然后入队entry
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.add(entry);
                } else {
                    //频率相同的情况
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }
        //4、 小根堆当中已经有了结果
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
        return ret;
    }
//    public static void main(String[] args) {
//        String[] words={"i","love","world","i","love","hello"};
//        List<String> ret=toKFrequent(words,2);
//        System.out.println(ret);
//    }


    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random =  map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


}





